#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class ZeroOneBag 
{
public:
	int Solution(vector<int> w, vector<int> v, int cap)
	{
		if (w.size() != v.size())
		{
			return -1;
		}
		memo.resize(w.size(), -1);
		return FindRev(0, w, v, cap);
	}

	int SolutionDP(vector<int> w, vector<int> v, int cap)
	{
		if (w.size() != v.size())
		{
			return -1;
		}
		return 0;
	}

private:
	int FindRev(int idx, vector<int> w, vector<int> v, int cap)
	{
		if (cap <= 0 || idx >= w.size())
		{
			return 0;
		}

		if (memo[idx] != -1 && cap >= w[idx])
		{
			return memo[idx];
		}

		int ret = FindRev(idx + 1, w, v, cap);
		if (cap >= w[idx])
		{
			ret = max(ret, v[idx] + FindRev(idx + 1, w, v, cap - w[idx]));
		}
		
		memo[idx] = ret;

		return ret;
	}

private:
	vector<int> memo;
};

int main(int ac, char* av[])
{
	vector<int> w{ 1,2,3 };
	vector<int> v{ 4,5,12 };
	int cap = 4;

	ZeroOneBag bag;
	auto res = bag.Solution(w, v, cap);

	return 0;
}